#pragma once

template<class Iterator>
void QuickSort(Iterator begin, Iterator end){
    if(end <= begin) return;
    auto low = begin, high = end;
    auto key = *begin;
    while(low < high){
        while(key<*high && low<high) high--;
        if(low==high) break;
        *low = *high;
        low++;
        while(*low< key && low<high) low++;
        if(low==high) break;
        *high = *low;
        high--;
    }
    *low = key;
    QuickSort(begin, low-1);
    QuickSort(low+1, end);
}

template<class Container>
void QuickSort(Container & a){
    QuickSort(std::begin(a), std::end(a)-1);
}
